package com.code.leetcode.center50;

import com.code.leetcode.utils.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/26 9:11
 */
public class The105 {

    Map<Integer, Integer> map = new HashMap<>();

    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int idx = 0;
        for (int num : inorder) {
            map.put(num, idx++);
        }
        return dfs(0, preorder.length - 1, 0, preorder.length - 1);
    }

    public TreeNode dfs(int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        if (preorderLeft > preorderRight) {
            return null;
        }
        int node = preorder[preorderLeft];
        Integer index = map.get(node);
        int leftTreeSize = index - inorderLeft;
        TreeNode root = new TreeNode(node);
        root.left = dfs(preorderLeft + 1, preorderLeft + leftTreeSize, inorderLeft, index - 1);
        root.right = dfs(preorderLeft + leftTreeSize + 1, preorderRight, index + 1, inorderRight);
        return root;
    }
}
